정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.
첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.
N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.
합성수를 소수의 곱으로 나타내는 방법이다.
입력 받은 정수 N을 loop문을 통해 계속 나눠줍니다.
for(int i = 2;i <= Math.sqrt(N);i++){
while(N % i == 0){
N /= i;
System.out.println(i);
}
}
if(N>1)
System.out.println(N);
정수 i로 나눠주는데 i의 범위는 2부터 N의 제곱근까지 입니다. 그 이후의 약수로 N을 나눈다면 몫이 N의 제곱근보다 작아지는데, 이 몫은 이미 loop를 통해 지나온 수이기 때문에 중복이 생깁니다.
즉 중복 없이 수행하려면 N의 제곱근까지를 범위로 해야합니다.
문제에 있던 테스트케이스를 예를 들자면 9991은 97, 103으로 소인수분해 되는데 103은 9991의 제곱근인 99.95 이상입니다.
loop를 끝내고 나온 N은 완전히 나누어져 1이거나 소수입니다. 1의 경우 소수가 아니니 출력을 제외하고 그 외에는 반드시 소수이기 때문에 출력해줍니다.
원래는 소수로 나눠주어야 하는데 N보다 작은 소수의 리스트를 따로 작성한 후 나누는 연산을 할 경우 리스트를 생성하는데 N*O(log N) 시간이 걸린다고 판단하였습니다.
한 정수 x가 소수인지 판별하는 알고리즘은 2 ~ x의 제곱근 범위의 수로 x를 나눌 때 나머지가 0이 되게 하는 수가 있는지 확인해야 합니다.
for(int i = 2;i <= Math.sqrt(x);i++){
if(x % i == 0){
return false; // 소수가 아님
}
}
return true; // 소수
위의 수행(소수인지 판별)은 O(log N) 시간이 걸리는데 N보다 작은 소수 리스트를 작성하려면 N번 반복해야하니 O(Nlog N)시간이 걸리는 것입니다.
반면, 소수 리스트를 작성하지 않은 Factorization의 수행 시간은 O(log N)입니다.
이중 loop긴 하나 log N 제곱 정도이고 이는 결국 O(log N)과 같다고 볼 수 있습니다.
감사합니다.
Text by Chaelin. Photographs by Unsplash.